package com.leetcode.partition8;

import java.util.ArrayList;
import java.util.List;

/**
 * @author `RKC`
 * @date 2021/10/26 10:34
 */
public class LC797所有可能的路径 {

    public static List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> answers = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        path.add(0);
        dfs(answers, path, graph, 0);
        return answers;
    }

    public static void main(String[] args) {
//        int[][] graph = {{1, 2}, {3}, {3}, {}};
        int[][] graph = {{4, 3, 1}, {3, 2, 4}, {3}, {4}, {}};
        System.out.println(allPathsSourceTarget(graph));
    }

    private static void dfs(List<List<Integer>> answers, List<Integer> path, int[][] graph, int startIndex) {
        if (startIndex == graph.length - 1) {
            answers.add(new ArrayList<>(path));
            return;
        }
        int size = getSize(graph[startIndex]);
        for (int next = 0; next < size; next++) {
            path.add(graph[startIndex][next]);
            dfs(answers, path, graph, graph[startIndex][next]);
            path.remove(path.size() - 1);
        }
    }

    private static int getSize(int[] arr) {
        int res = 0;
        for (int i : arr) {
            if (i != 0) res++;
        }
        return res;
    }
}
